//给定一个整数数组，返回所有数对之间的第 k 个最小距离。一对 (A, B) 的距离被定义为 A 和 B 之间的绝对差值。 
//
// 示例 1: 
//
// 
//输入：
//nums = [1,3,1]
//k = 1
//输出：0 
//解释：
//所有数对如下：
//(1,3) -> 2
//(1,1) -> 0
//(3,1) -> 2
//因此第 1 个最小距离的数对是 (1,1)，它们之间的距离为 0。
// 
//
// 提示: 
//
// 
// 2 <= len(nums) <= 10000. 
// 0 <= nums[i] < 1000000. 
// 1 <= k <= len(nums) * (len(nums) - 1) / 2. 
// 
// Related Topics 堆 数组 二分查找 
// 👍 173 👎 0

/**
 * @author DaHuangXiao
 */
package leetcode.editor.cn;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;

public class FindKThSmallestPairDistance {
    public static void main(String[] args) {
        Solution solution = new FindKThSmallestPairDistance().new Solution();
        solution.smallestDistancePair(new int[]{1,6,1},3);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        public int smallestDistancePair(int[] nums, int k) {
            Arrays.sort(nums);
            int l = 0;
            int r = nums[nums.length-1]-nums[0];
            System.out.println(r);

            while (l <= r) {
                int mid = l + (r - l) / 2;
                System.out.println(mid);
                System.out.println(count(mid, nums));
                if (count(mid, nums) >= k) {

                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            return l;
        }

        public int count(int dist, int[] nums) {
            int slow = 0;
            int ans = 0;
            for (int fast=0;fast<nums.length;fast++){
                while (nums[fast]-nums[slow]>dist){
                    slow++;
                }
                ans += fast-slow;
            }
            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

    }